package subject_set.lc200;

import java.util.Deque;
import java.util.LinkedList;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * @author haomin
 * @date 2022/12/18 23:21
 **/
public class Num19 {
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummyHead = new ListNode(-1, head);
            ListNode node1 = head;
            ListNode node2 = dummyHead;
            while(n-- > 0) node1 = node1.next;
            while(node1 != null) {
                node1 = node1.next;
                node2 = node2.next;
            }
            node2.next = node2.next.next;
            return dummyHead.next;
        }
    }

    class Solution2 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummyHead = new ListNode(-1, head);
            Deque<ListNode> s = new LinkedList<>();
            ListNode cur = dummyHead;
            while(cur != null) {
                s.push(cur);
                cur = cur.next;
            }
            while(n-- > 0) {
                s.pop();
            }
            cur = s.peek();
            cur.next = cur.next.next;
            return dummyHead.next;
        }
    }
}